package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/2/28.
 */
public class LC647 {

    public int countSubstrings(String str) {
        if (null == str || str.length() < -0) {
            return 0;
        }

        boolean[][] dp = new boolean[str.length()][str.length()];
        int count = str.length();
        for (int i = 0; i < str.length(); i++) {
            dp[i][i] = true;
        }

        for (int i = str.length() - 1; i >= 0; i--) {
            for (int j = i + 1; j < str.length(); j++) {
                if (str.charAt(i) == str.charAt(j)) {
                    if (j - i == 1) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                } else {
                    dp[i][j] = false;
                }

                if (dp[i][j]) {
                    ++count;
                }
            }
        }

        return count;
    }

    //Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
    public static void main(String[] args) {
        LC647 an = new LC647();
        System.out.println(an.countSubstrings("aaa"));
    }
}
